#include <iostream>

void merge(int *unsorted, int first, int mid, int last, int *sorted)
{
	int i = first;
	int j = mid;
	int k = 0;
	while (i < mid && j < last)
	{
		if (unsorted[i] < unsorted[j])
		{
			sorted[k++] = unsorted[i++];
		} else {
			sorted[k++] = unsorted[j++];
		}
	}

	while ( i < mid)
	{
		sorted[k++] = unsorted[i++];
	}
	while (j < last)
	{
		sorted[k++] = unsorted[j++];
	}

	for (int v = 0; v < k; ++v)
	{
		unsorted[first + v] = sorted[v];
	}
}


void merge_sort(int *unsorted, int first, int last, int *sorted)
{
	if (first + 1 < last)
	{
		int mid = (first + last) / 2;
		merge_sort(unsorted, first, mid, sorted);
		merge_sort(unsorted, mid,   last, sorted);
		merge(unsorted, first, mid, last, sorted);
	}

}

int main(int argc, char const *argv[])
{
	/* code */
	const int size = 10;
	int arr[size]={0};
	const int arr_len = sizeof(arr) / sizeof(int);

	printf("%s\n", "origin:");
	for (int i = 0; i < arr_len; ++i)
	{
		arr[i] = rand()%100;
		printf(" %d ", arr[i]);
	}

	int arr_tmp[arr_len]={0};

	merge_sort(arr, 0, arr_len, arr_tmp);

	printf("\n%s\n", "sorted:");
	for (int i = 0; i < arr_len; ++i)
	{
		printf(" %d ", arr[i]);
	}
	printf("\n");
	return 0;
}
